Introduction to Ramsey Theory
Seminar 11:09 <_llll_> i suggest you start when ready mark-t 11:09 combinatorics 11:10 * ChanServ changes topic to 'Seminar in progress, if you want to speak, say ! and wait to be called.' 11:10 all righty then 11:12 so, ramsey theory is all about showing that sufficiently large mathematical objects have a given structure 11:12 since I've never really studied it in detail, I'll just give a few well-known results in the area 11:13 first of all, consider this problem: in any group of six people, show that there is either a set of three people who all know each other, or a set of three people who are complete strangers 11:14 use the obvious assumptions: if person A knows person B, then person B knows person A, and two people are either strangers or they know each other 11:15 this is a pretty common problem; you've probably come across it in #math, even if you don't know any ramsey theory 11:15 I'll omit the proof for the time being, in case you want to think about it 11:17 now, here's one way of rewording this problem: given K_6, the complete graph on 6 vertices, and an assignment of one of two colors to each edge in the graph, show that there are 3 vertices such that the edges between them are all the same color 11:20 it turns out that this problem is answered directly by Ramsey's theorem, which is what ramsey theory is named after; Ramsey's theorem is as follows: 11:22 given j colors, we'll call them c_1, c_2, ..., c_j, and j positive integers, we'll call them n_1, n_2, ..., n_j, then for sufficiently large n, any way you could color the vertices of K_n with colors c_1, ..., c_j will have at least one subgraph with n_i vertices, all of whose edges are color c_i, for some i 11:23 the smallest such n is called a Ramsey number, and it is denoted by R(n_1, n_2, ..., n_j) 11:24 for our example problem, we wish to show that R(3,3) <= 6 11:25 it should be obvious that R(1,k) = R(k,1) = 1 and R(2,k) = R(k,2) = k for any k > 0 11:25 we'll prove Ramsey's theorem by induction on n_1 + n_2 + ... + n_j 11:26 ! 11:26 yes? 11:26 why =k is k is not smallest? 11:27 for R(2,k)? 11:27 yes 11:27 well, if you have less than k vertices, then all of the edges can be colored with c_2, which fails to have a set of two vertices colored with c_1 or a set of k vertices colored with c_2 11:29 is that clear? 11:29 can be k=3? 11:29 yes 11:29 so, R(2,3)=R(3,2)=3? 11:30 so R(2,3) = 3 says that any coloring of K_3's edges will either have a set of two vertices such that all the edges between them are color c_1, or a set of 3 vertices such that all the edges between them are color c_2, and that this isn't true for K_2 11:30 yes 11:31 and why not =2? 11:31 because K_2 has one edge, which you can color with c_2 11:32 that graph will not have two vertices connected by a c_1 edge, and it will not have three vertices connected by c_2 edges 11:33 ok 11:33 so, I claim that R(n_1, n_2, ..., n_j) <= R(n_1 - 1, n_2, ..., n_j) + R(n_1, n_2 - 1, ..., n_j) + ... + R(n_1, n_2, ..., n_j - 1) 11:34 each term has 1 subtracted from exactly one of the n_i terms 11:35 let the RHS of that inequality be n, and consider any coloring of K_n's edges 11:36 pick any vertex in K_n, let's call it v, and split the remaining vertices of K_n into j sets A_1, A_2, ..., A_j, where the elements of A_i are the vertices connected to v by an edge with color c_i 11:39 now, since n = 1 + |A_1| + |A_2| + ... + |A_j| = R(n_1 - 1, ...) + R(n_1, n_2 - 1, ...) + ... + R(..., n_j - 1), it follows that R(..., n_i - 1, ...) >= |A_i| for at least one i 11:40 for if R(..., n_i - 1, ...) < |A_i| for all i, then the RHS would be <= |A_1| + |A_2| + ... + |A_j| - j, which can't be 1 + |A_1| + ... + |A_j| 11:41 ! 11:41 yes? 11:41 are there (n-1) * n / 2 edges? 11:41 yes 11:42 so, look at one of these A_i where R(..., n_i - 1, ...) >= |A_i|; then, either A_i contains n_j vertices connected by edges of color c_j for j != i, or it contains n_i - 1 vertices connected by edges of color c_i 11:43 ! 11:43 in the former case, we're done; in the latter case, those n_i - 1 vertices along with the vertex v form a set of n_i vertices connected by edges of color c_i, as desired; so we're done 11:43 yes? 11:43 is sum{i} n_i = (n-1)*n/2 ? 11:43 no 11:45 so, this proof gives an upper bound for R(n_1, n_2, ..., n_j); it's actually a considerable over-estimate, but that doesn't matter; it's just an existence proof 11:47 now, if we use our fact that R(2,3) = R(3,2) = 3, our proof told us that R(3,3) <= R(2,3) + R(3,2) = 6, so that proves the initial question as well 11:48 now I'd like to share a proof for a lower bound of Ramsey numbers 11:48 ! 11:48 I'm only going to present it for the R(k,k) case, but it can easily be generalized; this result is due to Erdos 11:48 yes? 11:49 can be the parameters of R rotated? 11:49 yes 11:49 ! 11:49 yes? 11:50 if R has M parameters then there is M! Ramseys that are the same? 11:50 assuming the parameters are different 11:50 yes, assuming, of course. 11:51 it doesn't matter what order you list the numbers; there's nothing special about c_i and c_j that makes them somehow different 11:53 so, the idea for this proof is that we compute the expected number of single-color subgraphs of size k for a given n; if the expected number is less than 1, then there must be some coloring that has no single-color k-subgraphs, which means R(k,k) > n 11:56 for any choice of k vertices, the edges between them will be the same color in 2*2^{C(n,2)-C(k,2)} different colorings of K_n -- 2 is because there are two choices for what that same color will be, and 2^{C(n,2)-C(k,2)} is how many ways to color the remaining edges 11:56 ! 11:56 yes? 11:56 can exist non-colored edges? 11:56 no 11:58 ! 11:58 now, since there are C(n,k) different sets of k vertices, there are a total of C(n,k) * 2 * 2^{C(n,2)-C(k,2)} single-color k-subgraphs in all the colorings of K_n, and there are 2^{C(n,2)} total colorings of K_n 11:58 yes? 11:58 can be represented this graph by an upper triangular matrix modulo m-colors? 11:58 yes 12:00 ! 12:00 the expected value is just the ratio between the two, so we want to know when C(n,k) * 2 * 2^{-C(k,2)} < 1 12:00 yes? 12:00 the total of combinations is m^{(n-1) * n / 2} ? 12:00 yes 12:00 lol, continue 12:01 I don't want to bore you with algebra, but if you use some approximations, you can show that this means n > k/e * 2^{(k-1)/2} 12:02 er, n is less than that, R(k,k) is greater 12:04 of course, this proof isn't constructive; it just tells us that there has to be some coloring of K_n with no single-color k-subgraphs 12:04 constructive results are actually quite a bit behind this result 12:05 ok, so that's enough of ramsey numbers 12:05 here's another well-known result from ramsey theory, called Van der Waerden's theorem 12:07 ! 12:07 if you assign every positive integer one of j colors, for any k and sufficiently large n, there will be an arithmetic sequence of integers of length k, each one smaller than n, that all have the same color 12:07 yes? 12:07 inmho, i think that it can be better elaborated with algebra and prime numbers as colors, and some new operations 12:08 oh 12:08 so, you can count the numbers of each prime, etc. 12:09 that the primes don't divide each other 12:09 so, I'll give a quick proof for the case of two colors and an arithmetic sequence of length 3, then I'll describe how you can extend it to get the full theorem 12:12 look at numbers 1, 2, and 3; at least two of them must have the same color -- let's call them a_1 and a_2 and the color c_1; then, if a_1 + a_2 is colored c_1, we're done, so let's suppose it's colored with c_2 12:12 note that, at the most, a_1 + a_2 = 5 12:13 now, consider blocks of 5 consecutive numbers, that is {1,...,5}, {6,...,10}, {11,...,15}, and so on 12:13 there are 32 ways to color any given block, so by the time we've seen 33 blocks, we must have seen at least two with exactly the same coloring 12:14 let's call them {b_1 + 1, ..., b_1 + 5} and {b_2 + 1, ..., b_2 + 5} 12:15 from those blocks, we choose a_1 and a_2 such that b_1 + a_1 and b_1 + a_2 are the same color, with a_1 and a_2 chosen from {1,2,3} 12:17 and, if b_1 + a_1 is color c_1, then we have b_1 + a_1 + a_2 must be color c_2, and also b_2 + a_1 and b_2 + a_2 have color c_1 and b_2 + a_1 + a_2 have color c_2, since the {b_2 + 1, ..., b_2 + 5} block is colored exactly the same way 12:17 now, consider the number b_1 + b_2 + a_1 + a_2 12:18 this number, along with b_1 + a_1 and b_2 + a_2 form an arithmetic progression, and b_1 + a_1 and b_2 + a_2 are both color c_1 12:19 however, it also forms an arithmetic progression with b_1 + a_1 + a_2 and b_2 + a_1 + a_2, which are both colored c_2 12:20 therefore, whatever color we assign to it, it will complete an arithmetic progression of length 3, all of the same color 12:21 er, those indices aren't right 12:21 replace b_1 + b_2 with 2b_2 - b_1 and a_1 + a_2 with 2a_2 - a_1 -- they're the indices needed to complete an arithmetic progression 12:21 I was thinking of a different theorem 12:22 ok, so, once you do that, the proof of this case is complete 12:23 to extend it to more colors, instead of being forced to complete a sequence at 2b_2 - b_1 + 2a_2 - a_1, you're forced to use a third color; then, you repeat the process to find a number where these must converge 12:24 to extend it to longer sequences, you take all the places where I forced there to be two of a kind and replace them with the number to force a sequence of length k-1 12:24 ok, I'm done 12:26 ! 12:26 is known the formula of lower bound? 12:26 you can speak freely 12:27 I don't know; you can probably do something similar to Erdos's proof for Ramsey numbers 12:28 the exact formula is certainly unknown, but of course some lower bounds are known; I just don't know how good or bad they are 12:28 same order of magnitude off 12:28 understood 12:29 and now I go to sleep Category:Seminar Category:Ramsey Theory